package 哈希表;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/7 16:48
 */
public class leetcodeI两数之和 {
    /*
     梦开始的地方

     1. 哈希 + 遍历  O(N)  O(N)


     2. 排序 + 滑动窗口And双指针.双指针  O(N * lgN)   O(1)

    3. 排序 + 二分


     4.暴力 双重 for 循环   O(N ^ 2)  O(1)
     思考: 为什么 慢! , 上一次 的 循环 对于 当前 次循环 没有 任何的 帮助,也就是 上一次的
     O(N) 的对整个 数组的 遍历 对 当前没提供 任何 帮助,
     所以优化的点, 就是 之前 走过的 元素 数据 ,能不能 对 后面的 遍历元素 ,提供一些帮助 ( 这是 一个 非常  值得 思考的 点)
     也就是 之前 走过的 元素 (符合 某种 condition 是否 需要 缓存 一下, 后面可能 使用到!)

     */

    /*
      排序 + 滑动窗口And双指针.双指针
      思考 一下, 为为什么 需要 排序, 因为不排序的话,
      就没法 构造 双指针的 一个 单调性
      ==
      but 这样写 有问题, 题目 要求的 是  返回 , 原来数组中 元素的 位置,
      不是 排序后的 元素的 位置 ( 注意 )
     */
    public int[] solution(int nums[],int target){
        Arrays.sort(nums);
        int l = 0,r = nums.length - 1;
        while(l < r){
            if(nums[l] + nums[r] == target){
                return new int []{l,r};
            }
            else if (nums[l] + nums[r] > target){
                r--;
            }
            else{
                l++;
            }
        }
        return new int[]{};
    }
    /*
      上面方法的 解决办法:  关键点是   具有 单调性
      通过 index 数组 对下表 排序 后的一个 映射, 就可以 解决 上面的问题
      但是 O(N * logN)  O(N) 空间复杂度 就不是 O(1)了
      AC
     */
    public int []solutionNew(int nums[] ,int target){
        Integer index[] = new Integer[nums.length];
        for(int i = 0;i < nums.length;i++){
            index[i] = i;
        }
        Arrays.sort(index,(a,b) -> nums[a] - nums[b]);
        int l = 0,r = nums.length - 1;
        while(l < r){
            if(nums[index[l]] + nums[index[r]] == target){
                return new int[]{index[l],index[r]};
            }
            else if(nums[index[l]]  + nums[index[r]] > target ){
                r--;
            }
            else{
                l++;
            }
        }
        return null;
    }
    /*
    你发现还是所谓的 预处理！
    哈希表
     */
    public int[] map(int nums[],int target) {
        Map<Integer,Integer> map = new HashMap<>(nums.length);

        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(target - nums[i])){
                return new int []{i,map.get(target - nums[i])};
            }
            map.put(nums[i],i);
        }

        return null;
    }

}




